/*
 * @Author: 缄默
 * @Date: 2021-09-18 15:20:11
 * @LastEditors: 缄默
 * @LastEditTime: 2021-09-23 20:23:43
 */

 //单调栈结构

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

vector<vector<int>> rightWay(vector<int>& arr);

int main() {
    vector<int> arr({ 3,4,1,5,6,2,7 });
    vector<vector<int>> answer{ {1, 2}, {0, 2}, {-1, -1}, {2, 5}, {3, 5}, {2, -1}, {5, -1} };
    vector<vector<int>> res = rightWay(arr);
    for (auto x : answer) {
        for (auto y : x) {
            cout << y << " ";
        }
        cout << endl;
    }
    return 0;
}

vector<vector<int>> rightWay(vector<int>& arr) {
    stack<int> stack;
    vector<vector<int>> res(arr.size(), vector<int>(2));
    int num;
    for (int i = 0; i < arr.size(); i++)
    {


            while (!stack.empty() && arr[stack.top()] > arr[i])
            {
                num = stack.top();
                stack.pop();
                res[num][1] = i;
                res[num][0] = stack.empty() ? -1 : stack.top();
            }
            if (!stack.empty()) {
                res[i][0] = stack.top();
            }
            else
            {
                res[i][0] = -1;
            }

            stack.push(i);
    }
    while (!stack.empty())
    {
        num = stack.top();
        res[num][1] = -1;
        stack.pop();
    }
    return res;
}

